#ifndef __PRIMMINIMUMSPANNINGTREE__
#define __PRIMMINIMUMSPANNINGTREE__
#include <vector>
#include <utility>
#include <list>


class PrimTree{
public:
	PrimTree(int num):node_num_(num){}//constructor
	~PrimTree();//dispose
	void CreateGraph();//create a graph
	int GetWeight(char a, char b);//get weight value with their lables
	int LocateNode(char c);//locate a node with its lable
	int GetPrimTree(char d);//get a minimum spanning tree start with " char d"
protected:
	struct Node{
		char lable;
		Node * next;
		int key;
	};
private:
	int node_num_;
	Node ** graph_;
	typedef std::pair<char ,char> c_pair;
	typedef std::pair<c_pair, int> cw_pair;
	std::vector<cw_pair> weights_;
	std::list<Node*> que_;
	//get weight helper
	struct pair_equal_op
	: public std::binary_function<cw_pair ,c_pair, bool>{
		inline bool operator()(const cw_pair& w, const c_pair& c) const{
			return w.first == c;
		}
	};
	//queue sort helper
	struct less_key_cmp{
		inline bool operator()(Node* left, Node* right){
			if(left->key == right->key){
				return left->lable < right->lable;
			}else return left->key < right->key;
		}
	};
};
#endif